// 编写一个函数来查找字符串数组中的最长公共前缀。

// 如果不存在公共前缀，返回空字符串 ""。

// 示例 1:

// 输入: ["flower","flow","flight"]
// 输出: "fl"
// 示例 2:

// 输入: ["dog","racecar","car"]
// 输出: ""
// 解释: 输入不存在公共前缀。

#include <string>
#include <vector>

using namespace std;

// 暴力查找
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res{};
        for (int j{0}, sz_0 = strs[0].size(); j < sz_0; ++j) {
            char c = strs[0][j];
            for (int i{1}, sz = strs.size(); i < sz; ++i) {
                if (j >= strs[i].size() || strs[i][j] != c)
                    return res;
            }
            res += c;
        }
        return res;
    }
};

// 先排序，如果有共同前缀的话，一定会出现在首尾两端的字符串中，所以我们只需要找首尾字母串的共同前缀即可
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        int i{0};
        int len = min(strs[0].size(), strs.back().size());
        while (i < len && strs[0][i] == strs.back()[i]) ++i;
        return strs[0].substr(0, i);
    }
};

// 纵向扫描
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int m = strs.size(); // m行
        int n = strs[0].size(); // n列
        for (int j{0}; j < n; ++j) { // 先按列
            char c = strs[0][j];
            for (int i{1}; i < m; ++i) { // 再按行
                if (j == strs[i].size() || // 如果当前行的长度不够，就应该结束
                    strs[i][j] != c)
                    return strs[0].substr(0, j); // 返回第一个字符串的子串
            }
        }
        return strs[0];
    }
};

// 横向扫描，从长变短
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res{strs[0]};
        int n = strs.size();
        for (int i{1}; i <n; ++i) {
            res = longestCommonPrefix(res, strs[i]);
            if (res == "") break; // 如果前缀已经是空串，就不需要再继续
        }
        return res;
    }
    string longestCommonPrefix(const string& s0, const string& s1) {
        int n = min(s0.size(), s1.size());
        int i{0};
        while (i < n && s0[i] == s1[i]) ++i;
        return s0.substr(0, i);
    }
};

// 分治
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        return longestCommonPrefix(strs, 0, strs.size()-1);
    }
    string longestCommonPrefix(vector<string>& strs, int lhs, int rhs) {
        if (lhs == rhs) return strs[lhs];
        int mid = lhs + (rhs - lhs) / 2;
        string lcp_left = longestCommonPrefix(strs, lhs, mid);
        string lcp_right = longestCommonPrefix(strs, mid + 1, rhs);
        return longestCommonPrefix(lcp_left, lcp_right);
    }
    string longestCommonPrefix(const string& s0, const string& s1) {
        int n = min(s0.size(), s1.size());
        for (int i{0}; i < n; ++i) {
            if (s0[i] != s1[i]) return s0.substr(0, i);
        }
        return s0.substr(0, n);
    }
};

#include "../stdc++.h"

// 纵向扫描
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res{};
        // 找最短的字符串
        int n{INT_MAX};
        for (auto& s : strs) {
            int len = s.size();
            if (len < n) {
                n = len;
            }
        }
        for (int i{0}; i < n; ++i) {
            char c = strs[0][i];
            for (auto& s : strs) {
                if (s[i] != c) {
                    return res;
                }
            }
            res += c;
        }
        return res;
    }
};